## Cyclic reduction of polynomials and cyclic product

from PyM import *

K = Zn(41)

[_,x] = polynomial_ring(K,'x')

def cyclic_reduction(f,n):
    r = degree(f)
    a = coeffs_inc(f)
    for j in range(n,r+1):
        c = a[j]
        if c==0: continue
        f = f-c*x**j; f = f+c*x**(j%n)
    return f

def cyclic_product(f,g,n): return cyclic_reduction(f*g,n)


f=polynomial([1,2,3,4,3,2,1],x)
    
show(cyclic_reduction(f,4)>>K)

show(cyclic_reduction(1+2*x+3*x**2+4*x**3,3)>>K)
    
show(cyclic_reduction(sum(geometric_series(x,25)),10)>>K)

[_,a0,a1,a2,a3,a4,x] = multivariate_polynomial_ring(K,'a0','a1','a2','a3','a4','x')

A = a0+a1*x+a2*x**2+a3*x**3+a4*x**4

show(cyclic_reduction(A,3)>>K)

show(cyclic_reduction(A,1)>>K)

show(cyclic_product(1+2*x**2+3*x**3+5*x**5,1+x+7*x**7,6)>>K)

show(cyclic_product(a0+a1*x+a2*x**2,x**2,3)>>K)